CMU 15-445/645 — Fall 2024 Projects

参考 课程网站，项目地址，测试网站，Discord 频道。尝试做一下新版的项目。

Project #0 - C++ Primer

Task #1 & Task #2

算法设计

HyperLogLog 主要用于近似计算 multiset 中的基数（不同元素的数量），相比精确计算需要的 \(O(n)\) 空间 \(n\) 为基数的大小），该算法只需要使用很少的内存。

基本想法是，使用哈希函数将多重集合的元素映射到均匀分布的随机数上，然后记录最左或者最右连续 \(0\) 的最大数量。利用哈希值的随机性，某个比特位为零的概率是 \(\frac{1}{2}\)，如果最多 \(n\) 个连续的零，则估计多重集合的基数为 \(2^{n}\)，因为该哈希值出现的概率是 \(\frac{1}{2^{n}}\)。

不过该算法方差较大，只要有一个哈希值包含很多零，就会严重高估基数。所以，可以将多重集合拆分为多个子集，通常是利用哈希值的前 \(k\) 个比特位确定元素拆分到的桶，然后每个桶内维护剩余比特位中连续零的最大值，取加权平均值 \(2^{\frac{1}{m}\sum_{i=1}^{m}{R_{i}}}\) 得到每个桶的平均基数（其中 \(m=2^{k}\)），然后再乘以 \(m\) 得到多重集合的基数估计值。

额外的优化是使用 constant=0.79402 和调和平均来提升准确率，使用稀疏布局和密集布局来平衡内存开销和准确率，最后计算公式如下。（参考 HyperLogLog in Presto: A significantly faster way to handle cardinality estimation，A problem so hard even Google relies on Random Chance，HyperLogLog）

$$ CARDINALITY_{HLL}=constant\cdot m\cdot \frac{m}{\sum_{i=1}^{m}2^{-R_{i}}} $$

注意事项

① n_bits 的范围可以确定下限是 0，上限不确定，如果很大会内存溢出。② 很多地方使用的是无符号整数，在使用字面量时需要声明后缀（例如 1UL），以及做算术运算时需要避免溢出（例如取负值时需要转为有符号数）。③ 做移位操作 1 << x 时需要注意 x 的大小，如果结果超出表示范围则行为未定义。经过测试不同环境 1 << 32 会得到 0 或者 1。④ 可以使用 ./test/hyperloglog_test --gtest_filter=HyperLogLogTest.EdgeTest1 执行指定的测试。

Project #1 - Buffer Pool Manager

Task #1 - LRU-K Replacement Policy

设计思路

简单的实现，使用单个哈希表维护 frame_id 到 LRUKNode 的映射关系，LRUKNode 负责维护该页面的最后 k 次访问时间戳，在淘汰时通过扫描整个哈希表来确定需要淘汰哪个 frame_id，淘汰的时间复杂度为 \(O(n)\)。如果使用两个链表分别维护 <k 和 >=k 的 Frame 访问顺序，如果不考虑 Pin，那么可以 \(O(1)\) 时间实现淘汰。但是由于不知道 Frame 是否被 Pin，所以仍然需要遍历链表查找第一个未被 Pin 的 Frame。也可以使用类似 TreeMap 的结构，直接存储未被 Pin 的所有 Frame，按照次数、时间戳排序，淘汰的时间复杂度是 \(O(\log{n})\)，不过每次访问都需要重新删除插入来保证排序。（实际上都差不多，因为 BPM 的主要瓶颈在磁盘 I/O）

Task #2 - Disk Scheduler

设计思路

比较有意思的设计就是毒丸（poison pill），队列中存储的是 std::optional<bustub::DiskRequest> 类型的元素，向队列中添加 std::nullopt 元素，表示终止工作线程的执行。

Task #3 - Buffer Pool Manager

设计思路

缓冲池的基本功能就是获取 Frame，可以从空闲列表或者淘汰 Frame 来获取。如果是通过淘汰获取，则需要删除 Frame 和 Page 的映射关系、将脏页刷盘以及重置 FrameHeader。然后可以将 Frame 和 Page 关联，需要设置 Frame 和 Page 的映射关系、设置 FrameHeader 的成员变量、从磁盘读取数据、调用 LRUK 相关函数。

最后可以将该 Frame 和 PageGuard 关联，由于 PageGuard 会获取 Frame 的读写锁，所以要在创建 PageGuard 之前解锁 BPM 独占锁，从而避免 BPM 阻塞在 Frame 的锁上。例如，典型的情况是有两个线程同时对相同的 Page 获取 WritePageGuard。

线上测试就只有 BufferPoolManagerTest.SchedulerTest (0/0) 没有过，花几个小时找 BUG 都没找到，最后还是简单暴力打印日志解决问题。只能说别想太多，问题出在 is_dirty_ 的设置位置不对，我在 GetDataMut 方法中设置，而即使不调用该方法，NewPage 得到的空白页面也算是脏页，所以要在构造函数中设置。而且，调用 FlushPage/FlushAllPages 之后不应该将脏页标志重置，因为只要 WritePageGuard 还在那么页面依然可能变脏。（如果在刷盘的过程中修改页面，或许会产生问题，应该在刷盘之前获取 Frame 的读写锁，但是要避免和 BPM 独占锁产生死锁，这个点暂时不做）

Leaderboard Task (Optional)

方案一（×）

简单的想法是在磁盘 I/O 时不持有 BPM 锁，而是直接解锁然后在磁盘 I/O 结束之后加锁。但是在如下交错下，相同的页面会占用多个 Frame（Problem #1）。解决方式也有，就是在解锁 BPM 之前更新 Page 和 Frame 之间的映射关系。但是会有新的并发问题，也就是之后的线程判断 Page 在缓冲池中，然后直接读写该 Frame，而此时之前的脏页还没有刷盘，Page 数据也没有读取到 Frame 中（Problem #2）。

Problem #1
thread A -> fetch page 1 -> bpm lock -> evict -> bpm unlock (t1) -> dirty flush
thread B -> fetch page 1 -> bpm lock (t2) -> evict (error)

Problem #2
... -> bpm lock -> evict -> update map -> bpm unlock (t1) -> dirty flush
... -> bpm lock (t2) -> exist -> bpm unlock -> frame lock -> read/write page (error)

所以需要在解锁 BPM 之前给 Frame 加独占锁，但是这样做需要调整代码结构来避免死锁，也就是把 BPM 级别的共享变量的更新都放在解锁 BPM 之前，从而避免之后再加锁 BPM。这里给 Frame 加锁不会像之前一样阻塞 BPM，因为此时的 Frame 不被任何 PageGuard 持有。如果 Page 在缓冲池中，设置 Replacer 相关的数据一定要持有 BPM 锁，因为淘汰时只会加 BPM 锁，要避免页面在淘汰之后立即被访问的情况。（特殊情况可以不加，但是要注意如何设置值）

Problem #3
... -> frame lock -> bpm unlock (t1) -> dirty flush -> bpm lock (deadlock)
... -> bpm lock (t2) -> exist -> bpm unlock -> frame lock (deadlock) -> read/write page

Problem #4
... -> bpm lock -> exist page 1 -> frame lock -> bpm unlock (t1) -> access page 1 (t4)
... -> bpm lock (t2) -> evict page 1 (t3) -> ...

这样还是有问题，就是淘汰的 Frame 在包含脏页刷盘时会解锁 BPM，而此时如果有线程获取该 Page，则会从磁盘读取到旧页面或者此时磁盘中没有该页面（如果该页面是 NewPage）。此时需要额外维护哈希表存储相关信息，使用额外的锁来保护，该锁需要在解锁 BPM 之前持有，否则依然会发生上述错误。如果当前读取的 Page 还没有完成刷盘，则直接从旧 Frame 复制到当前 Frame 中。可以发现使用这种解锁 BPM 的方案会有各种问题，这都是我上次实现时遇到过的，最后 QPS 从 3700+ 反向优化到 1000+。

Problem #4
... -> bpm lock -> evict page 1 -> bpm unlock (t1) -> dirty flush
... -> fetch page 1 -> bpm lock (t2) -> disk read

方案二（×）

主要瓶颈在单个 BPM 独占锁，可以使用类似 Java 的 ConcurrentHashMap 的思路，将 BPM 锁拆分成多个锁。由于不能使用外部现有的并发库，那么可以使用哈希表数组，根据 Page 的编号映射到不同哈希表中。如果需要同时锁定多个分区，则需要按照顺序加锁来避免死锁，可以使用 std::scoped_lock。还有很多坑点和方案一类似，最后 QPS 从 3700+ 反向优化到 900+。

Problem #1
thread A -> bpm lock 1 -> bpm lock 2 (deadlock)
thread B -> bpm lock 2 -> bpm lock 1 (deadlock)

方案三（√）

可以不使用额外的锁，而是设置标志位表示该页面正在刷盘或者读取中，例如在 Page 到 Frame 的哈希表中记录无效的 Frame 编号，然后其他获取线程使用条件变量等待执行完成。需要注意等待的条件是哈希表中不存在该 Page 映射或者对应 Frame 编号有效，因为如果空闲列表为空且无法淘汰其他 Frame，则需要手动删除该临时键值对而不会设置有效的 Frame 编号。此时可以在磁盘 I/O 时解锁 BPM，之后加锁修改标志位，然后唤醒线程。

如果磁盘调度器不使用线程池，则 QPS 反向优化到 900+。如果使用单队列 + 8 线程，则 QPS 优化到 5300+。实际上不使用磁盘调度器的后台线程，而是直接调用 Schedule 方法，QPS 可以到 14700+。使用单队列 + 16 线程，则 QPS 优化到 14000+，因为工作线程总共有 16 个。

如果为每个线程分配一个队列，任务循环放置到每个队列，则 QPS 只有 11000+。有延迟场景性能更低可能是因为没有任务窃取机制，某个线程没被调度导致相应队列的任务积压。但是无延迟场景的 QPS 更接近不使用后台线程的情况，因为各个线程不必竞争相同队列的锁。（该优化会有问题，如果存在对同一页面的多个磁盘 I/O 请求，可以想到的情况是主动 Flush 脏页，会存在多个对相同页面的写请求，无法保证顺序）

由于测试使用 8 个 Scan 线程顺序读，8 个 Get 线程随机写（使用 Zipfian 分布）。由于第三个测试结果的权值最大，主要优化第三个场景，也就是顺序读每 0.1ms 执行一次，随机写每 1ms 执行一次。理论上最大 QPS 是 88000，目前看来 Scan 操作的 QPS 优化空间较大。

scan_qps_large / 1000 + get_qps_large / 1000 + scan_qps_small / 1000 + get_qps_small / 1000 + scan_qps_1ms + get_qps_1ms

经过测试，Scan 操作的缓存命中率都是 0%，使用优先淘汰策略（不论优先淘汰什么类型）的 Scan 操作 QPS 可以提升到 30000+。使用默认的 LRUK 淘汰策略、优先淘汰只被 Scan 访问的 Frame、优先淘汰只被 Get 访问的 Frame 的 Get 操作命中率和 QPS 分别是 7% 5800+、11% 4300+ 和 3% 6500+。

虽然按理说优先淘汰只被 Scan 访问的 Frame 比较正常，因为 Scan 线程是顺序读本身就无法利用缓存，提前淘汰不会影响性能。基于单队列 + 16 线程的代码，可以将 QPS 从 14000+ 优化到 42000+。但是实际上优先淘汰任意访问类型的 Frame 都可以得到差不多的 QPS，因为只要提升 Evict 的速度，就可以大幅提升 Scan 操作的 QPS。另外，命中率更高的 Get 操作 QPS 反而更低，真不知道什么原因。

排名

Rank	Submission Name	scan_qps_large	get_qps_large	scan_qps_small	get_qps_small	scan_qps_1ms	get_qps_1ms	QPS
98	ALEX	41513	4156	48125	643	3433	248	3776
24	ALEX	19407	19844	17793	21289	2491	2788	5358
16	ALEX	107110	104764	99692	102739	8370	5930	14715
18	ALEX	13775	13869	14001	16822	8148	5829	14035
22	ALEX	70177	70478	65910	73478	5775	5049	11105
4	ALEX	19866	10945	20708	13994	37939	4325	42330